package com.spd.sort;

/**
 * 给定一个数组，选择其中第i大、或者第i小的元素。
 * 该算法时间复杂度为O(n)。不停的调用快排中的一次过程，来划分，这样中间的元素
 * 则是排在第i位的元素。
 * 时间复杂度为O(n)，比快排的O(nlg(n)) 还要快。它的二分之后，不需要去管当前比较值不在的那一边。
 * 只需要管自己所在的这一边。
 * @author xianchao
 *
 */
public class RandomizedSelect {

	private int[] array = null;
	
	public void init(int[] array) {
		this.array = array;
	}
	
	/**
	 * 
	 * @param array 要比较的数组
	 * @param p 最左边位置
	 * @param r 最右边位置
	 * @param i 需要排位的位次
	 * @return
	 */
	public int select(int p, int r, int i) {
		if(p == r) {
			return array[p];
		}
		int q = partition(p, r);
		int k = q - p + 1;
		if(i == k) {
			return array[q];
		} else if(i < k) {
			return select(p, q - 1, i);
		} else {
			return select(q + 1, r, i - k);
		}
	}
	
	/**
	 * 快速排序中的划分。
	 * @param p
	 * @param r
	 * @return
	 */
	public int partition(int p, int r) {
		//排序中的临时变量，分别表示小于基准值，大于基准值的元素下标
		int i = p - 1;
		for(int j = p; j < r; j++) {
			if(array[j] <= array[r]) {
				i++;
				int temp = array[j];
				array[j] = array[i];
				array[i] = temp;
			}
		}
		//最后依次，把基准值 r 和下标为i + 1的元素进行交换
		int temp = array[r];
		array[r] = array[i + 1];
		array[i + 1] = temp;
		return i + 1;
	}
	
	public static void main(String[] args) {
		RandomizedSelect randomizedSelect = new RandomizedSelect();
		int[] array = new int[]{10, 9, 23, 15, 35, 24, 17, 21, 1, 8};
		randomizedSelect.init(array);
		//查找从小到大排序的时候，排第4位的值。
		int result = randomizedSelect.select(0, array.length - 1, 4);
		System.out.println(result);
	}
}
